package xyz.scootaloo.oj.offer

import org.junit.Test
import xyz.scootaloo.console.app.support.Tester

/**
 * @author flutterdash@qq.com
 * @since 2021/4/12 10:18
 */
class P53I {

    /**
     * input:  5, 7, 7, 8, 8, 10   target: 8
     * step.1           ^          通过二分查找找到第一个目标值的下标, 假如目标值不存在则返回一负数并退出
     *                 l,r
     * step.2        l     r       尝试将左右指针分别向左右移动, 直到越界, 或者碰到不等于目标值的位置停止
     * step.3        l        r    移动完成后, l=2, r=5, sum = r-l-1 = 2
     */
    private fun search(nums: IntArray, target: Int): Int {
        var l = nums.binarySearch(target)
        if (l < 0)
            return 0

        var r = l
        while (l >= 0 && nums[l] == target)
            l--
        while (r < nums.size && nums[r] == target)
            r++

        return r - l - 1
    }

    @Test
    fun test0() {
        Tester.createTest(this::testFun0)
            .addCase(Wrapper(intArrayOf(5, 5, 5, 7, 7, 8, 8, 10, 10, 10, 10), 10), 4)
            .addCase(Wrapper(intArrayOf(5, 5, 5, 7, 7, 8, 8, 10, 10, 10, 10), 5), 3)
            .addCase(Wrapper(intArrayOf(5, 5, 5, 7, 7, 8, 8, 10, 10, 10, 10), 7), 2)
            .addCase(Wrapper(intArrayOf(5, 5, 5, 7, 7, 8, 8, 10, 10), 10), 2)
            .addCase(Wrapper(intArrayOf(5, 7, 7, 8, 8, 10), 6), 0, true)
            .testAndShow()
    }

    private fun testFun0(input: Wrapper): Int {
        return search(input.input, input.target)
    }

    inner class Wrapper(val input: IntArray, val target: Int)

}
